Internet Info 1994 March

home *** CD-ROM | disk | FTP | other *** search

/ Internet Info 1994 March / Internet Info CD-ROM (Walnut Creek) (March 1994).iso / inet / internet-drafts / draft-rekhter-direct-provider-00.txt < prev next >

Wrap

Text File | 1993-10-26 | 18.8 KB | 506 lines

- 1 - Network Working Group Y. Rekhter INTERNET DRAFT T.J. Watson Research Center, IBM Corp. <draft-rekhter-direct-provider-00.txt> October 1993 Selecting a Direct Provider Status of this Memo This document is an Internet Draft. Internet Drafts are working documents of the Internet Engineering Task Force (IETF), its Areas, and its Working Groups. Note that other groups may also distribute working documents as Internet Drafts. Internet Drafts are draft documents valid for a maximum of six months. Internet Drafts may be updated, replaced, or obsoleted by other documents at any time. It is not appropriate to use Internet Drafts as reference material or to cite them other than as a ``working draft'' or ``work in progress.'' Please check the 1id-abstracts.txt listing contained in the internet-drafts Shadow Directories on nic.ddn.mil, nnsc.nsf.net, nic.nordu.net, ftp.nisc.sri.com, or munnari.oz.au to learn the current status of any Internet Draft. 1 Introduction Within the existing Internet routing architecture/protocols different hosts within a domain (autonomous system) usually can't control the choice of adjacent domains for forwarding of the inter-domain traffic originated by the hosts. In this document we describe a simple mechanism that provides hosts with such control. The proposed scheme can be realised with the existing technology, off-the shelf components, and minor tweaking of forwarding algorithm by border routers. The scheme doesn't require any new routing protocols. Expiration Date April 1994 [Page 1] - 2 - 2 Background The Internet is viewed as a set of arbitrary interconnected Autonomous Systems (Domains). An autonomous system that carries transit traffic is called a service provider (or just a provider). An autonomous system that uses other autonomous system(s) to carry locally originated traffic is called a service subscriber (or just a subscriber). A provider that has an external neighbor (in the BGP/IDRP sense) with one of the BGP/IDRP speakers within a subscriber is called the direct provider (with respect to the subscriber). All other providers are called indirect (with respect to the subscriber). Routers that participate in inter-domain routing are called Border Routers or Border Intermediate Systems (BISs). Within the current Internet routing the choice of routes available to a host within a subscriber is limited to the routes selected by the BISs within the subscriber. Consequently, a route available from a direct provider, but not selected by the BISs within the subscriber can't be made available to a host within the subscriber. As an illustration of this limitation consider the following topology: H1 B \ / \ \ / \ \ / \ D A / \ / / \ / / \ / / \/ H2 C where A is a BIS that belong to domain RD-A, B is a BIS that belongs to domain RD-B, C is a BIS that belongs to domain RD-C, and D is a BIS that belongs to domain RD-D. H1 and H2 are two hosts in RD-D. D has to select between B and C as the next hop domain (BIS) to destinations in RD-A. Consequently, hosts within RD-D, H1 and H2, would be bounded by the D's choices. If H1 would prefer to use route to destinations in RD-A going through B, and H2 would prefer to use route to destinations in RD-A going through C, then superficially one Expiration Date April 1994 [Page 2] - 3 - would conclude that such route selection can't be satisfied within the current Internet routing. The following shows that such a conclusion is incorrect. 3 Solving the problem The problem of removing the limit of choices imposed on hosts within a subscriber by subscriber's BISs can be decomposed into three orthogonal, but somewhat related subproblems: - how a BIS within a subscriber that is connected to a particular direct provider learns about routes offered by the provider - how a router within a subscriber discovers a BIS that is connected to a particular direct provider - how to find a correct exit BIS - how to ensure forwarding within the subscriber that is consistent with the host's preference of the direct provider This document assumes that each provider has a globally unambiguous identifier that can be used both for the purpose of distributing routing information and for the purpose of packet forwarding. Furthermore, the document assumes that the autonomous system number (AS number) is used as such an identifier. 3.1 How a BIS discovers routes offered by a direct provider With BGP/IDRP ([1], [2]) a BIS stores the routes received from an external neighbor in the Adj-RIB-In (adjacency Routing Information Base input) associated with the neighbor. For each external neighbor the BIS also knows the AS number of the provider the neighbor is in. Therefore, for each direct provider that has an external neighbor with a BIS, the BIS has sufficient information about the routes offered by the provider, as well as the provider's identifier (AS number). Expiration Date April 1994 [Page 3] - 4 - 3.2 How to find a correct exit BIS A BIS that is connected to a particular provider needs to pass the information about this connectivity to other BISs within its domain. This is accomplished by generating and propagating (via BGP/IDRP) to all of the BIS's internal neighbors (in BGP/IDRP sense) a route whose AS-PATH (RD-PATH) path attribute contains only the AS number of the provider and whose NLRI may be either empty or embeds the AS number. The choice of empty NLRI is determined by a particular routing protocol (whether the protocol allows to carry AS-PATH (RD-PATH), but no NLRI). Since this route is distributed to all the BISs within the subscriber, any BIS within the subscriber can identify a BIS that has an external neighbor within a particular direct provider. The situation is a bit more complex for routers within the subscriber that are not BISs (they don't participate in BGP/IDRP). We suggest two possible schemes. Option 1: The first option requires the BIS that has an external neighbor with a particular provider to generate an intra-domain route to a destination that unambiguously identifies the AS number of the provider. The Network Layer Reachability Information (NLRI) of such a route can be constructed by by embedding the AS number in an IP address. Option 2: The second option assumes that routers within a subscriber that don't participate in BGP/IDRP have a default route pointing to particular BISs (this default route may be either static or dynamic). Such a route would result in forwarding a packet whose destination is outside the subscriber to one of the BISs within the subscriber. Once the packet reaches the BIS, the BIS determines an appropriate exit BIS using information received via BGP/IDRP. To provide correct operations it is essential that there be a consistent scheme for embedding AS numbers into IP addresses. A possible scheme for doing this is suggested in SDRP [3], where an AS number is embedded in the lower two octets of the 128.0.0.0 IP network number. For example, AS number 233 is encoded as 128.0.0.233. Expiration Date April 1994 [Page 4] - 5 - 3.3 How to provide consistent forwarding Providing forwarding that takes into account direct provider preferences requires an additional mechanism. This is because routes selected by BISs within a subscriber may not be consistent with the preferences of a particular host within the subscriber. The mechanism should be able to identify the host's preference for the purpose of packet forwarding. In this document we assume that a packet may carry certain explicit information that identifies a particular provider. In general, this information can be carried as either an IP option or via an encapsulation. This document assumes the use of encapsulation, such as SDRP [3] or GRE [4]. When a host originates a packet, and the host has a certain preference with respect to a particular direct provider, the host needs to indicate this preference. The host can indicate it either by itself or by relying on some proxy agent (e.g. first hop router). To indicate the preference for a particular direct provider the packet is encapsulated (by either the originating host, or by its proxy agent) and the destination address in the outer header embeds the AS number of the provider. If the information about direct providers is distributed via intra- domain routing (Option 1 in Section 3.2), then the packet will be forwarded via intra-domain routing procedures to the correct exit BIS. The exit BIS will use the destination address in the outer header to determine the direct provider. The BIS then will decapsulate the packet and will use the destination address in the inner header of the packet to determine whether the Adj-RIB-In associated with the provider has a route to the destination specified in the original packet. If such a route exists, then the BIS will forward the packet to the neighbor associated with the Adj-RIB-In. Otherwise, the original packet will be forwarded using BIS's FIB (using normal forwarding procedures). The BIS may generate an ICMP Destination Unreachable message back to the entity that performed the encapsulation ( either the host that originated the packet, or its proxy agent) to indicate that the route through the provider desired by the host is unavailable. If the information about direct providers is not distributed via intra-domain routing (Option 2 in Section 3.2), then the packet will be forwarded via a default route to one of the BISs within the Expiration Date April 1994 [Page 5] - 6 - subscriber. If that BIS happen to be a correct exit BIS (the BIS peers with an external neighbor, such that the neighbor belongs to the provider indicated by the packet), then the BIS will operate as described in the previous paragraph. Otherwise, the packet will be encapsulated one more time with the destination address in the outer header indicating the correct exit BIS. Once the packet reaches the correct exit BIS, the outer header will be stripped and the remaining processing will be performed precisely as described in the previous paragraph. This document assumes that within a subscriber that offers support for direct provider selection all the BISs trap packets whose destination indicates embedded provider identifier (AS number) and decapsulate these packets before forwarding them to external neighbors. If a BIS receives a packet whose destination indicates embedded provider identifier, and the BIS determines that the provider is not a direct provider of the subscriber the BIS is in, the BIS should generate an ICMP Destination Unreachable message to the entity that performed the encapsulation (either the host that originated the packet or some proxy agent acting on behalf of the host). The entity should use this message as an indication that the selected provider is unavailable. A host (or its proxy agent) is not required to maintain information about all the direct providers of the subscriber the host is in. If a host (or its proxy agent) specifies a provider that is not a direct provider of the subscriber, then packets originated by the host (or its proxy agent) will be forwarded based on the choices of the direct provider made by the BISs within the subscriber. When a host (or its proxy agent) receives an ICMP Destination Unreachable message indicating unavailability of the route through a particular provider, the host (or its proxy agent) should either change its selected provider or should stop using direct provider selection mechanism altogether. 3.4 An example of operations We illustrate how the proposed scheme operates using the topology described in Section 2. Assume that D prefers routes through B to destinations in A, but when connectivity to B fails or B doesn't have Expiration Date April 1994 [Page 6] - 7 - routes to destinations in A, D would switch to routes through C. The routes selected by D are consistent with H1's choices for the direct provider (use B as a primary, use C as a fallback), but are in conflict with H2's choices for the direct provider (use C as a primary, use B as a fallback). To satisfy H2's preferences for the direct provider, H2 encapsulates its outgoing packets, such that the destination address in the outer header embeds C's AS number. When such a packet reaches D, D uses the destination address to identify the Adj-RIB-In associated with C, performs decapsulation, and then checks whether the Adj-RIB-In has a route to the destination specified in the inner header. If such a route exists, then the packet is forwarded to C. Otherwise, the packet is forwarded using D's FIB, which results in forwarding the packet to B. If the connectivity between C and A is present, then D will forward the packets originated by H2 through C. When the connectivity is disrupted the D's Adj-RIB-In that is associated with C will not have a route to destinations in A, so D will forward the packets through B. In this case D will generate an ICMP Destination Unreachable message back to H2. H2 is expected to use this message as an indication that route through the selected provider is unavailable. To illustrate how the proposed scheme operates when a host selects a provider who is not a direct provider of the subscriber the host is in, assume that H2 selects X as its direct provider. In this case H2 will receive an ICMP Destination Unreachable message either from a BIS or from some other router within the subscriber, and should use this message as an indication that no route through the selected provider (X) is available. 4 Multiple preferences A host (or its proxy agent) may have preferences for more than one direct provider. The list of such preferences may be either ordered (first try direct provider X, if that is impossible then try direct provider Y, etc...), or unordered (try a direct provider X, but if not available pick at random another provider from the list). The proposed scheme doesn't allow to simultaneously specify multiple choices for direct providers. That is, a packet contains identity of only one preferred provider. The host (or its proxy agent) relies on the ICMP Destination Unreachable messages to determine the feasibility of using the direct provider selected by the host. Expiration Date April 1994 [Page 7] - 8 - 5 Limitations The proposed scheme supports only a "soft" selection. That is, if a route through a selected provider isn't available, or the selected provider is not a direct provider of the subscriber the host is in, the subscriber will use its selected direct provider. This proposal doesn't distinguish between the case where a host selects a provider who is not a direct provider of the subscriber the host is in, and the case where a host selects a direct provider, but there is no route through that provider. While the proposed solution may be suitable to solve other problems, such a discussion is outside the scope of this document. Specifically, suitability of the proposed solution to an arbitrary policy-based routing problem (a.k.a. "arbitrary internet" (AI) problem) is outside the scope of this document. 6 Conclusions This document describes how the existing routing protocols combined with encapsulation and minor changes to forwarding algorithm can be used to solve the problem of direct provider selection. It provides the same dynamic rerouting capabilities as available with the existing routing architecture/protocols. The scheme doesn't require introduction of any new routing protocols and/or new network layer protocol - it is based pretty much on existing off-the-shelf components. The functionality provided by the scheme described in the document is quite similar to the "long-distance" provider selection available in today's telephony, where a caller (host) can either use the long- distance carrier (direct provider) selected by the RBOC the caller is attached to, or may explicitly indicate its preference for a particular long long-distance carrier. The scheme may be used in similar circumstances to enable "long-distance" provider selection functionality in the Internet. While the scheme is described in terms of IP, it can be directly applicable to other existing connectionless network layer protocols, like CLNP. Expiration Date April 1994 [Page 8] - 9 - 6 Acknowledgements This proposal was largely stimulated by discussions with Robert Brenner (GTE) and Peter Ford (LANL). The author would like to express his deep thanks and appreciation to Susan Hares (MERIT), Tony Li (cisco Systems), and Jessica Yu (MERIT) for their review and constructive comments. References [1] Rekhter, Y., Li, T., `A Border Gateway Protocol 4 (BGP-4)', Internet Draft, April 1993 [2] Hares, S., `IDRP for IP', Internet Draft, March 1993 [3] Estrin, D., Zappala, D., Li, T., Rekhter, Y., "Source Demand Routing: Packet Format and Forwarding Specification (Version 1)" Internet Draft, September 1993 [4] Hanks, S., Li, T., Farinacci, D., Traina, P., "Generic Routing Encapsulation (GRE)", Internet Draft, September 1993 Security Considerations Security issues are not discussed in this memo. Author's Addresses Yakov Rekhter T.J. Watson Research Center IBM Corporation P.O. Box 218 Yorktown Heights, NY 10598 Phone: (914) 945-3896 email: yakov@watson.ibm.com Expiration Date April 1994 [Page 9]